function [ mainFtPts ] = ExtractFtPts( vSignature, triangles  )
%COMPVERTSEGMENTATION Summary of this function goes here
%   Detailed explanation goes here


nbV=size(vSignature,1);
nbTri=size(triangles,1);

% Data structure for the vertex connectivity
vToV= cell(nbV,1);     
for i=1:nbTri
    vToV(triangles(i,1))={[cell2mat(vToV(triangles(i,1))),triangles(i,2)]};
    vToV(triangles(i,2))={[cell2mat(vToV(triangles(i,2))),triangles(i,1)]};
    
    vToV(triangles(i,2))={[cell2mat(vToV(triangles(i,2))),triangles(i,3)]};
    vToV(triangles(i,3))={[cell2mat(vToV(triangles(i,3))),triangles(i,2)]};
    
    vToV(triangles(i,3))={[cell2mat(vToV(triangles(i,3))),triangles(i,1)]};
    vToV(triangles(i,1))={[cell2mat(vToV(triangles(i,1))),triangles(i,3)]};
end
% Remove duplicated elements in the array to connected vertices
for i=1:nbV
    vToV(i)={unique(cell2mat(vToV(i)), 'first')};
end


% Sort vertices according to how much concave/convex is the local shape
convexity=zeros(size(vSignature,2),1);
for i=1:nbV
    %diff=vSignature(i,:)-ones(1,size(vSignature,2));
    %convexity(i)=diff*diff';
    convexity(i) = 1 / norm(vSignature(i,:));
end

[~,convexitySorted]=sort(convexity,'descend');
%vToSelect=round(nbV*1/3);
vToSelect=round(nbV * 0.2);               % 0.2
convexitySorted=convexitySorted(1:vToSelect);

% Compute the vertices that are together and extract the center vertex
[mainFtPts] = ExtractMainFtPtsUsingConvexity(convexity,convexitySorted,vToV);

% Using the main feature points, find vertices with similar signature
%[ allSeg ] = ComputeSegmentation( mainFtPts, vProbability, vToV  );
%WriteSegments(allSeg);

end

function [mainFtPts] = ExtractMainFtPtsUsingConvexity(convexity,convexitySorted , vToV)

segments={};

nbV=size(vToV,1);
vToSegment=false(nbV,1);
vToSegment(convexitySorted)=true;
markedV=false(nbV,1);


while true
    % Seed of the segment
    idx=find(markedV(convexitySorted)==0,1,'first');
    currSeg=convexitySorted(idx);
    currSegFlag=false(nbV,1);
    currSegFlag(currSeg)=1;
    while true
        connV=false(nbV,1);
        connVList=[vToV{currSeg}];
        connV(connVList)=true;
        addVToSeg=(vToSegment & connV);
        currSegFlag=currSegFlag | addVToSeg;
        newCurrSeg=find(currSegFlag~=0);
        if numel(currSeg)==numel(newCurrSeg)
            % The segment stops growing, no more vertices added
            segments(numel(segments)+1)={newCurrSeg};
            break;
        end
        currSeg=newCurrSeg;    
    end
    % Update the vertex flag for the new segment
    markedV=markedV | currSegFlag;
    % If all marked vertices are those to segment, we stop
    if ~any(xor(markedV,vToSegment))
        break;
    end
    
end

% Remove small segments, number of vertices < 5
cleanSegments={};
for i=1:numel(segments)
    if numel(segments{i}) > 3
        cleanSegments(numel(cleanSegments)+1)=segments(i);
    end
end

% Write the segments for debugging
% WriteSegments(cleanSegments);

% Extract the main feature point for each segment
mainFtPts=zeros(numel(cleanSegments),1);
for i=1:numel(cleanSegments)
    [~,idx]=max(convexity(cleanSegments{i}));
    mainFtPts(i)=cleanSegments{i}(idx);
end

end


function [ allSeg ] = ComputeSegmentation( mainFtPts, vProbability, vToV  )

global matchVThreshold;

nbV=size(vToV,1);
allSeg={};
i=1;
markedV=false(nbV,1);
while i<nbV
    if numel(allSeg)==numel(mainFtPts)
        break;
    end
    
    % Find the starting vertex of the current segment
    vID=mainFtPts(numel(allSeg)+1);
    assert(markedV(vID)==0);
    
    seg=vID;                % initial segment: contains only one vertex
    segBoundary=seg;        % segment boundary
    markedV(vID)=true;
    % Grow the segment from that vertex
    while true
        % find a vertex connected to the boundary and those minimum probability to vertices of seg is maximal
        maxProb=0;
        maxProbV=0;
        % For each vertex of the boundary (or border) of the segment
        j=1;
        while j<=numel(segBoundary)
            boundaryV=segBoundary(j);
            boundaryVToV=vToV{boundaryV};
            % For vertex connected to the boundary vertex
            nbMarkedV=0;
            for k=1:numel(boundaryVToV)
                nextV=boundaryVToV(k);
                if markedV(nextV)
                    nbMarkedV=nbMarkedV+1;
                    continue;
                end
                prob=min(vProbability(nextV,seg));
                if prob>maxProb
                    maxProb=prob;
                    maxProbV=nextV;
                end
            end
            if nbMarkedV==numel(boundaryVToV)
                [~,IX]=find(segBoundary~=boundaryV);
                segBoundary=segBoundary(IX);
            else
                j=j+1;
            end
        end
        
        % If the probability value is to low, we stop growing the segment
        if maxProb < matchVThreshold
            allSeg(numel(allSeg)+1)={seg};
            break;
        end
        % Add the vertex to the segment
        seg=[seg,maxProbV];
        segBoundary=[segBoundary,maxProbV];
        markedV(maxProbV)=true;
        
    end
end

end

function [ ] = WriteSegments( allSeg, nbSeg  )

[filename, pathname] = uiputfile('*.txt', 'Select the txt file');
filename=strcat(pathname, filename);

fileID = fopen(filename, 'w');

if(fileID==-1)
    disp(['Cannot open file ',filename]);
    return;
end

if nargin==1
    nbSeg=numel(allSeg);
end

for i=1:nbSeg
    tmp=cell2mat(allSeg(i));
    for j=1:numel(tmp)
        fprintf(fileID,'%d ',tmp(j));
    end
    fprintf(fileID,'\n');
end
fclose(fileID);
end
